import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author ZhiWen Ren
 * @version 1.0
 * @description: LeetCode-84-柱状图中最大的矩形
 * @date 2025/7/2 15:32
 */
public class Solution84 {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        if (n == 1) {
            return heights[0];
        }
        int[] left = new int[n];
        int[] right = new int[n];
        int ans = 0;
        Deque<Integer> monoStack = new ArrayDeque<>();

        // 确定每根柱子的左边界
        for (int i = 0; i < n; i++) {
            while (!monoStack.isEmpty() && heights[monoStack.peek()] >= heights[i]) {
                // 出栈
                monoStack.pop();
            }
            left[i] = (monoStack.isEmpty() ? -1 : monoStack.peek());
            monoStack.push(i);
        }
        monoStack.clear();

        // 确定每根柱子的右边界
        for (int i = n - 1; i >= 0; i--) {
            while (!monoStack.isEmpty() && heights[monoStack.peek()] >= heights[i]) {
                // 出栈
                monoStack.pop();
            }
            right[i] = (monoStack.isEmpty() ? n : monoStack.peek());
            monoStack.push(i);
        }

        // 遍历每根柱子的左右边界确定最大面积
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }
}
